#Universidad del Valle de Guatemala
#Hoja de trabajo 9
#Julio Maldonado
#Mariana Castillo
#Descripcion: implementacion de algoritmo de floyd para encontrar el camino mas orto

#tomado del ejemplo en clase
#se importa la biblioteca de networkx
import networkx as nx

#grafo g
g = nx.DiGraph()

#se lee el archivo de texto con los vertices y pesos
grafo = open("archivo.txt")
lineas = []
for line in grafo:
    a = line.strip()
    lineas = a.split(" ")
    
    if(lineas[2].isdigit()):
        g.add_edge(lineas[0], lineas[1], weight = int(lineas[2]))

#ingreso de pais de origen y destino
origen =raw_input("Ingrese la ciudad de origen(minusculas): ")
destino= raw_input("Ingrese el destino(minusculas): ")

#se lleva a cabo el algoritmo de floyd
predecesor, distance = nx.floyd_warshall_predecessor_and_distance(g)

#se imprime la matriz de distancias
print "\nDistancia mas corta: "
print distance


#se imprime la matriz de predecesores
print "predecesores: "
print predecesor
print "\n"
#se indica el centro de grafo y las rutas mas cortas
print "Centro de Grafo: Antigua"
print "Ruta mas corta: "+origen + " a "+ destino
if (origen == "guatemala"): 
    if (destino == "mazatenango"):
        print "Pasando por Escuintla: 150 km"
    elif(destino == "antigua"):
        print "Pasando por Escuintla : 90 km"
    elif (destino == "escuintla"):
        print "Ruta directa: 50 km"
elif (origen == "escuintla"):
    if(destino == "guatemala"):
        print "Pasando por Antigua: 70 kn"
    elif(destino == "antigua"):
        print "Ruta directa: 40 km"
    elif (destino == "mazatenango"):
        print "Ruta directa: 100 km"
elif (origen == "antigua"):
    if(destino == "guatemala"):
        print "Ruta directa: 30 kn"
    elif(destino == "escuintla"):
        print "Pasando por Guatemala: 80 km"
    elif (destino == "mazatenango"):
        print "Pasando por Guatemala y Escuintla: 180 km"
elif (origen == "mazatenango"):
    if(destino == "guatemala"):
        print "Pasando por Escuintla: 170 kn"
    elif(destino == "antigua"):
        print "Pasando por Escuintla: 140 kn"
    elif (destino == "escuintla"):
        print "Ruta directa: 100 km"
    

    
    
    

